package leetcode.offer_two_special.heap;

import java.util.*;

/**
 * @author mazouri
 * @create 2021-09-16 12:27
 */
public class _61_kSmallestPairs {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((o1, o2) -> o2[0] + o2[1] - o1[0] - o1[1]);

        int minNum1 = Math.min(k, nums1.length);
        int minNum2 = Math.min(k, nums2.length);

        for (int i = 0; i < minNum1; i++) {
            for (int j = 0; j < minNum2; j++) {
                if (maxHeap.size()<k){
                    maxHeap.offer(new int[]{nums1[i],nums2[j]});
                }else if (maxHeap.peek()[0]+maxHeap.peek()[1] > nums1[i]+nums2[j]){
                    maxHeap.poll();
                    maxHeap.offer(new int[]{nums1[i],nums2[j]});
                }
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int[] arr : maxHeap) {
            res.add(Arrays.asList(arr[0],arr[1]));
        }
        return res;
    }
}
